package 竞赛.周赛215;

import com.sun.security.jgss.GSSUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 第三题.java
 * @Description TODO
 * @createTime 2020年11月15日 11:01:00
 * 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
 *
 * 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,4,2,3], x = 5
 * 输出：2
 * 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
 * 示例 2：
 *
 * 输入：nums = [5,6,7,8,9], x = 4
 * 输出：-1
 * 示例 3：
 *
 * 输入：nums = [3,2,20,1,1,3], x = 10
 * 输出：5
 * 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
 */
public class 第三题 {
    public static void main(String[] args) {
        Solution solution=new Solution();
        int[] a={3,2,20,1,1,3};
        int i = solution.minOperations(a, 10);

        System.out.println(i);

    }
    static class Solution {
        ArrayList<Integer> temp=new ArrayList<>();
        public int minOperations(int[] nums, int x) {
            ArrayList<Integer>  list=new ArrayList<>();
            for(int a:nums){
                list.add(a);
            }

            back(x,0,list);
            if(temp.size()==0){
                return -1;
            }
            temp.sort(Comparator.naturalOrder());

            System.out.println(temp.toString());
            return temp.get(0);
        }



        public  void back(int x,int res,ArrayList<Integer> list){
            if(x==0){
                temp.add(res);
                return;
            }
            if (x < 0||list.size()<=0) {
                return ;
            }

            int[] map={list.get(0),list.get(list.size()-1)};

            if(map[1]>map[0]){
                int a=map[1];
                map[1]=map[0];
                map[0]=a;
            }


            for(int i=0;i<map.length;i++){
                if(x<map[i]){
                    return ;
                }
                x-=map[i];
                res++;
                if(i==0){
                    list.remove(0);
                }else {
                    list.remove(list.size()-1);
                }
                back(x,res,list);
                res--;
                x+=map[i];
                if(i==0){
                    list.add(0,map[i]);
                }else {
                    list.add(map[i]);
                }

            }

        }
    }
}
